package Demo87;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 迷宫中离入口最近的出口
 * https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/
 */

class Solution {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] vis;
    int m,n;
    public int nearestExit(char[][] maze, int[] e) {
        m = maze.length;n = maze[0].length;
        vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {e[0],e[1]});
        vis[e[0]][e[1]] = true;
        int ret = 0;
        while(!q.isEmpty()) {
            int sz = q.size();
            ret++;
           while(sz > 0) {
               int[] t = q.poll();
               int a = t[0], b = t[1];
               for(int i = 0; i < 4; i++) {
                   int x = a + dx[i], y = b + dy[i];
                   if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.') {
                       if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return ret;
                       q.add(new int[] {x, y});
                       vis[x][y] = true;
                   }
               }
               sz--;
           }
        }
        return -1;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        int ret = solution.nearestExit(new char[][]{{'+', '+', '.', '+'}, {'.', '.', '.', '+'}, {'+', '+', '+', '+'}}, new int[]{1, 2});
        int ret = solution.nearestExit(new char[][]{{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}}, new int[]{1,0});
        System.out.println(ret);
    }
}